# 0-1背包问题，每个元素只能使用一次，重量和价值都是元素内容

# 1、dp[j] 当前层包含元素（如i层包含0~i个元素）且背包容量为j所能达到的最大价值 j：0~target
# 2、递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])
# 3、初始化：全部初始化为0
# 4、遍历顺序:从左到右
# 5、打印dp数组


def getResult(nums):
    if sum(nums) % 2 != 0:
        return False
    target = int(sum(nums)/2)
    dp = [0] * (target + 1)
    # 更新len(nums)次
    for i in range(len(nums)):
        for j in range(len(dp)-1, nums[i] - 1, -1):
            # if j >= nums[i]:
            dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])

    # for i in dp:
    #     print(i, end=" ")
    if dp[target] == target:
        return True
    else:
        return False


nums = [4,4,4,4,4,4,4,4,8,8,8,8,8,8,8,8,12,12,12,12,12,12,12,12,16,16,16,16,16,16,16,16,20,20,20,20,20,20,20,20,24,24,24,24,24,24,24,24,28,28,28,28,28,28,28,28,32,32,32,32,32,32,32,32,36,36,36,36,36,36,36,36,40,40,40,40,40,40,40,40,44,44,44,44,44,44,44,44,48,48,48,48,48,48,48,48,52,52,52,52,52,52,52,52,56,56,56,56,56,56,56,56,60,60,60,60,60,60,60,60,64,64,64,64,64,64,64,64,68,68,68,68,68,68,68,68,72,72,72,72,72,72,72,72,76,76,76,76,76,76,76,76,80,80,80,80,80,80,80,80,84,84,84,84,84,84,84,84,88,88,88,88,88,88,88,88,92,92,92,92,92,92,92,92,96,96,96,96,96,96,96,96,97,99]
result = getResult(nums)
print(result)
